package algorithms;

import java.util.ArrayList;
import java.util.List;
import java.util.Set;

public class Problem140 {
	public List<String> wordBreak(String s, Set<String> wordDict) {
        if (s == null || "".equals(s)) 
        	return new ArrayList<String>();
        int[] dp = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            if (wordDict.contains(s.substring(0, i + 1))) dp[i] = 1;
            else {
                for (int j = 0; j < i; j++) {
                    if (dp[j] == 1 && wordDict.contains(s.substring(j + 1, i + 1))) {
                        dp[i] = 1;
                        break;
                    }
                }
            }
        }
        if (dp[s.length() - 1] == 0) 
        	return new ArrayList<String>();
        return wordBreak(s, dp, s.length() - 1, wordDict);
    }

    private List<String> wordBreak(String s, int[] dp, int end, Set<String> wordDict) {
        List<String> result = new ArrayList<String>();
        for (int i = 0; i < end; i++) {
            if (dp[i] == 1 && wordDict.contains(s.substring(i + 1, end + 1))) {
                List<String> temp = wordBreak(s, dp, i, wordDict);
                for (String str : temp) 
                	result.add(str + " " + s.substring(i + 1, end + 1));
            }
        }
        if (wordDict.contains(s.substring(0, end + 1))) 
        	result.add(s.substring(0, end + 1));
        return result;
    }
}
